//
// Created by Administrator on 2021/7/2.
//
// 找岛屿的最大面积
#include <vector>
#include <iostream>
#include <queue>
#include <stack>

using namespace std;

class Solution {
private:
    int maxIslandArea = 0;
    const vector<pair<int, int>> movement{{1,  0},
                                          {-1, 0},
                                          {0,  1},
                                          {0,  -1}};
public:
    /**
     * 主函数
     * @param grid
     * @return
     */
    int maxAreaOfIsland(vector<vector<int>> &grid) {
        int m = (int) grid.size(), n = (int) grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    countIslandArea(grid, m, n, i, j);
                }
            }
        }
        return this->maxIslandArea;
    }

    /**
     * bfs执行函数
     * @param grid
     * @param seen
     * @param i
     * @param j
     */
    void countIslandArea(vector<vector<int >> &grid, int m, int n, int i, int j) {
        queue<pair<int, int>> q;
        q.emplace(i, j);
        grid[i][j] = 0;
        int sizeCount = 0;
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            ++sizeCount;
            for (auto &move:this->movement) {
                // 判断四周四个格子是不是没见过的陆地,是的话加入队列
                int newRow = p.first + move.first;
                int newCol = p.second + move.second;
                if (newRow >= 0 and newRow < m and newCol >= 0 and newCol < n
                    and grid[newRow][newCol] == 1) {
                    q.emplace(newRow, newCol);
                    // 搜索过的地点置为0
                    grid[newRow][newCol] = 0;
                }
            }
        }
        // 更新最大值
        this->maxIslandArea = max(this->maxIslandArea, sizeCount);
    }

};

class Solution2 {
public:
    /**
     * 栈实现dfs
     * @param grid
     * @return
     */
    int maxAreaOfIsland(vector<vector<int>> &grid) {
        int ans = 0;
        for (int i = 0; i != grid.size(); ++i) {
            for (int j = 0; j != grid[0].size(); ++j) {
                int cur = 0;
                stack<int> stacki;
                stack<int> stackj;
                stacki.push(i);
                stackj.push(j);
                while (!stacki.empty()) {
                    int cur_i = stacki.top(), cur_j = stackj.top();
                    stacki.pop();
                    stackj.pop();
                    if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() ||
                        grid[cur_i][cur_j] != 1) {
                        continue;
                    }
                    ++cur;
                    grid[cur_i][cur_j] = 0;
                    int di[4] = {0, 0, 1, -1};
                    int dj[4] = {1, -1, 0, 0};
                    for (int index = 0; index != 4; ++index) {
                        int next_i = cur_i + di[index], next_j = cur_j + dj[index];
                        stacki.push(next_i);
                        stackj.push(next_j);
                    }
                }
                ans = max(ans, cur);
            }
        }
        return ans;
    }
};


class Solution3 {
public:
    /**
     * 队列实现bfs
     * @param grid
     * @return
     */
    int maxAreaOfIsland(vector<vector<int>> &grid) {
        int ans = 0;
        for (int i = 0; i != grid.size(); ++i) {
            for (int j = 0; j != grid[0].size(); ++j) {
                int cur = 0;
                queue<int> queuei;
                queue<int> queuej;
                queuei.push(i);
                queuej.push(j);
                while (!queuei.empty()) {
                    int cur_i = queuei.front(), cur_j = queuej.front();
                    queuei.pop();
                    queuej.pop();
                    if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() ||
                        grid[cur_i][cur_j] != 1) {
                        continue;
                    }
                    ++cur;
                    grid[cur_i][cur_j] = 0;
                    int di[4] = {0, 0, 1, -1};
                    int dj[4] = {1, -1, 0, 0};
                    for (int index = 0; index != 4; ++index) {
                        int next_i = cur_i + di[index], next_j = cur_j + dj[index];
                        queuei.push(next_i);
                        queuej.push(next_j);
                    }
                }
                ans = max(ans, cur);
            }
        }
        return ans;
    }
};


int main() {
    vector<vector<int>> grid{{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                             {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                             {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                             {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
                             {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
                             {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                             {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                             {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};
    vector<vector<int>> grid2{{1, 1, 0, 0, 0},
                              {1, 1, 0, 0, 0},
                              {0, 0, 0, 1, 1},
                              {0, 0, 0, 1, 1}};
    Solution sol;
    cout << sol.maxAreaOfIsland(grid);
    return 0;
}

